Jump Game || Gas Station

发表于

Jump Game

Question

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Analysis

遍历整个数组，利用reach标记当前可达的最大脚标，假如i>reach则停止遍历，判断此时i是否等于数组长度，假如可达的话，i应该恰好在des处停止

注意： i<=reach，而非 i<reach,初始条件下 i=reach=0

Code

  1. Greedy
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public boolean canJump(int[] nums) {
        int des=nums.length;
        if(des<2)   return true;
        int i=0;
        for(int reach=0;i<des&&i<=reach;i++){
            reach=Math.max(reach,i+nums[i]);
        }
        return (i==des)?true:false;
    }
}

Gas Station

Question

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Analysis

一开始只想着从每个节点开始遍历一圈，确认gas_total>=cost_total，TLE

LeetCode Discuss

  • 假如当前车站A(begin)无法到达B，则A-B的所有车站都无法到达B，begin从i+1开始
  • gas_total>=cost_total,即有路可寻

Code

  1. Greedy Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total=0,temp=0,begin=0;
        for(int i=0;i<gas.length;i++){
            temp=temp+gas[i]-cost[i];
            if(temp<0){
                begin=i+1;
                total+=temp;
                temp=0;
            }
        }
        return (total+temp<0)?-1:begin;
    }
}
  1. TLE version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total=0;
        int res=-1;
        
        for(int i=0;i<gas.length;i++){
            res=helper(i,gas,cost);
            if(res!=-1) 
                return res;
        }
        
        return -1;
    }
    
    public int helper(int begin, int[] gas, int[] cost){
        int total=0;
        int N=gas.length;
        for(int i=begin;i-begin<N;i++){
            int index=(i%N);
            total+=gas[index]-cost[index];
            if(total<0)
                return -1;
        }
        return begin;
    }
}